package Top_Interview_Questions.Bit_Manipulation;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @Author: 吕庆龙
 * @Date: 2020/1/30 20:42
 * <p>
 * https://leetcode-cn.com/problems/single-number/solution
 * /xue-suan-fa-jie-guo-xiang-dui-yu-guo-cheng-bu-na-y/
 */
public class _0136 {

    public static void main(String[] args) {
        _0136 test = new _0136();
        int[] nums = new int[]{4, 1, 2, 1, 2};
        System.out.println(test.singleNumber3(nums));
    }

    /*----------------------------------------位运算异或----------------------------------------*/

    /**
     * 原理:
     * https://leetcode-cn.com/problems/single-number/solution
     * /zhi-chu-xian-yi-ci-de-shu-zi-by-leetcode/
     */
    public int singleNumber3(int[] nums) {
        int ans = nums[0];
        if (nums.length > 1) {
            for (int i = 1; i < nums.length; i++) {
                ans = ans ^ nums[i];
            }
        }
        return ans;
    }

    /*----------------------------------------------------------------------------------------*/



    /*----------------------------------------hash表------------------------------------------*/

    /**
     * #.hash表,简单说就是键值映射关系
     * #.主要的用法就是hashMap
     */
    public int singleNumber2(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (Integer i : nums) {
            Integer count = map.get(i);
            count = count == null ? 1 : ++count;
            map.put(i, count);
        }
        for (Integer i : map.keySet()) {
            Integer count = map.get(i);
            if (count == 1) {
                return i;
            }
        }
        return -1; // can't find it.
    }

    /*----------------------------------------------------------------------------------------*/


    /**
     * 输入: [4,1,2,1,2]
     * 输出: 4
     */
    public int singleNumber1(int[] nums) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 1; i++, i++) {
            if (nums[i] != nums[i + 1]) {
                return nums[i];
            }
        }
        return nums[nums.length - 1];
    }
}
